1. Field of the Invention
The present invention relates to testing encryption and decryption algorithms and modes. Specifically, the preferred embodiment of the present invention relates to testing encryption hardware which previously required large amount of test time and test data to test encryption algorithms used in encryption devices. The present invention is especially applicable to low power, hardware cryptographic token applications.
2. Discussion of the Related Art
Referring to FIG. 1, the field the present invention involves a production tester 100 performing testing on a cryptographic system (product) 102. The cryptographic system 102 is either a single integrated circuit or a system including several integrated circuits. The product 102 under test includes at least a cryptographic function implementation 103. The cryptographic function implementation 103 is either hardware-based, software-based, or some combination of software with special hardware support. The production tester 100 includes a pattern generating portion that produces input test vectors 105 to input to the product 102. The production tester 100 also includes a logic analyzer section for receiving output test vectors 106 from the product 102. The production tester 100 will typically run a test program 101 which includes selected values for the input test vectors 105 and the expected correct output test vectors 106 for any specific product 102. The input test vectors 105 are typically chosen so as to fully exercise the product 102. If any part of the product 102 is flawed, the output test vectors 106 will not match the precomputed expected (correct) results stored in the test program 101, and the product 102 under test will fail production testing.
There are a very large number of possible input permutations and states in the cryptographic implementation. Because it is desirable to fully test the hardware cryptographic circuitry, T, which represents the number of test blocks is usually made to be very large. Assuming that the portion of circuitry tested during a particular cryptographic cycle i is a random P fraction of the total hardware, then the total test coverage F fraction of the total hardware is 1-(1-P).sup.T. This means that in order to achieve a high fault coverage, the number of test message blocks T is increased. Unfortunately, however, the T test blocks TB(1) through TB(T) are stored in the test program 101 as cryptographic test data 104. If since P is a low number, T must be large to achieve high fault coverage, and all this test data 104 is stored in the test program 101. It is undesirable to maintain a large amount of test data 104 in the test program 101. Even if a program were written which would generate test data without requiring large data storage, it would be undesirable to occupy the input vector lines for a lengthy cryptographic test, since this would forestall further tests which must be performed on the other parts of the product 102. Thus the total test time increases since the cryptographic function test must occur serially with the other tests.
Block cryptographic algorithms operate on blocks of plaintext and ciphertext. Often 64 bits is the block size of both input blocks and output blocks. The simplest way to use a cryptographic algorithm is to encrypt each input block P to produce the output block C. Here EECB(P)=C. This is called electronic codebook (ECB) mode. Electronic codebook mode derives its name from the fact that each unique input plaintext block always encrypts to the same output ciphertext block. The term "codebook" implies that a lookup table of codes could be formulated. However, because the typical block size is 64 bits, such a table would require 2.sup.64 entries, which is far too large to precompute and store. Furthermore, a different codebook exists for each possible key value. Electronic codebook decryption is simply the inverse cryptographic process.
Electronic Codebook Encryption (ECB) EQU C.sub.i =E(P.sub.i)
Electronic Codebook Decryption (ECB) EQU P.sub.i =D(C.sub.i)
The concept of chaining uses a feedback mechanism, because the results of the encryption of previous blocks are fed back into the encryption of the current block. This means that the previous encryption result is used to modify the encryption of the current block. Therefore, every encrypted output block is dependent not only upon the current input block, but upon all previous input blocks.
In cipher block chaining mode (CBC) encryption, the input plaintext block is XORed with the previous output ciphertext block before it is encrypted. After each encryption, the resulting ciphertext output block is stored in a feedback register to be bitwise XORed with the next input block. The decryption process is similar. As each input ciphertext block is decrypted, it is also saved in a feedback register. After the next ciphertext block is decrypted, an XOR operation is performed on the result of the feedback register.
Cipher Block Chaining Mode (CBC) Encryption EQU C.sub.i =E(P.sub.i XOR C.sub.i-1)
Cipher Block Chaining Mode (CBC) Decryption EQU P.sub.i =D(C.sub.i)XOR C.sub.i-1
In each of the above equations, an initial value vector (IV) is used to provide the feedback value CO for the first iteration.
In Cipher Feedback Mode (CFB) encryption, each ciphertext output block is the bitwise exclusive or of the encryption of the previous ciphertext and the plaintext. The Cipher Feedback Mode decryption takes advantage of the commutate nature of the XOR function that if A XOR B=C, then A=B XOR C. Therefore, the encryption function is used again even though decryption is being performed.
Cipher Feedback Mode (CFB) Encryption EQU C.sub.i =E(C.sub.i-1)XOR P.sub.i
Cipher Feedback Mode (CFB) Decryption EQU P.sub.i =E(C.sub.i-1)XOR C.sub.i
In the Output Feedback Mode (OFB) encryption, the cryptographic engine's input for each block is the engine's output from the previous block. The cryptographic engine begins with an initial value (IV) as plaintext data input. By block i, the engine has recursively performed encryption starting from the initial value i times, denoted by E.sup.i (IV). This mode also takes advantage of the commutative property of the exclusive or operation, and thus the encryption function E.sup.i (IV) is the same during both encryption and decryption.
Output Feedback Mode (OFB) Encryption EQU C.sub.i =E.sup.i (IV)XOR P.sub.i
Output Feedback Mode (OFB) Decryption EQU P.sub.i =E.sup.i (IV)XOR C.sub.i
The table below illustrates the encryption state of the cryptographic engine and the logical configuration implemented. E represents an encryption state of the cryptographic accelerator, and D represents a decryption state of the cryptographic accelerator.
______________________________________ Mode Encryption C.sub.i = Decryption P.sub.i = ______________________________________ ECB E (P.sub.i) D (C.sub.i) CBC E (P.sub.i XOR C.sub.i-1) D (C.sub.i) XOR C.sub.i-1 OFB E (C.sub.i-1) XOR P.sub.i E (C.sub.i-1) XOR C.sub.i OFB E.sup.i (IV) XOR P.sub.i E.sup.i (IV) XOR C.sub.i ______________________________________
In order to test all the above modes, the problem is the large amount of test time and test data 104 in the test program 101 required to test encryption algorithms used in encryption devices. Especially devices designed for low power, hardware token applications.
Previously, testing and verification were performed using costly external test vectors to obtain the desired test coverage. Additional tests were also required for each of the commonly used feedback modes. The use of external test vectors resulted in extraordinarily large test time required in which to validate the device. This added significantly to the overall expense of manufacturing the module. Another major problem with the previous solution was that the testing of the module stalled testing of other modules contained in the since each module was verified serially. Also prior solutions failed to address the serious problem of excessive time and RAM requirements for Power-On-Self-Test (POST) in the field.